A time-memory tradeoff using distinguished points: New analysis & FPGA results
Identifieur interne : 001A55 ( Main/Exploration ); précédent : 001A54; suivant : 001A56A time-memory tradeoff using distinguished points: New analysis & FPGA results
Auteurs : Francois-Xavier Standaert [Belgique] ; Gael Rouvroy [Belgique] ; Jean-Jacques Quisquater [Belgique] ; Jean-Didier Legat [Belgique]Source :
- Lecture notes in computer science [ 0302-9743 ] ; 2002.
Descripteurs français
- Pascal (Inist)
- Wicri :
- topic : Cryptographie.
English descriptors
- KwdEn :
Abstract
In 1980, Martin Hellman [1] introduced the concept of cryptanalytic time-memory tradeoffs, which allows the cryptanalysis of any N key symmetric cryptosystem in O(N) operations with O(N) storage, provided a precomputation of O(N) is performed beforehand. This procedure is well known but did not lead to realistic implementations. This paper considers a cryptanalytic time-memory tradeoff using distinguished points, a method referenced to Rivest [2]. The algorithm proposed decreases the expected number of memory accesses with sensible modifications of the other parameters and allows much more realistic implementations of fast key search machines. We present a detailed analysis of the algorithm and solve theoretical open problems of previous models. We also propose efficient mask functions in terms of hardware cost and probability of success. These results were experimentally confirmed and we used a purpose-built FPGA design to perform realistic tradeoffs against DES. The resulting online attack is feasible on a single PC and we recover a 40-bit key in about 10 seconds.
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: 000138
- to stream PascalFrancis, to step Curation: 000019
- to stream PascalFrancis, to step Checkpoint: 000121
- to stream Main, to step Merge: 001A65
- to stream Main, to step Curation: 001A55
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">A time-memory tradeoff using distinguished points: New analysis & FPGA results</title><author><name sortKey="Standaert, Francois Xavier" sort="Standaert, Francois Xavier" uniqKey="Standaert F" first="Francois-Xavier" last="Standaert">Francois-Xavier Standaert</name><affiliation wicri:level="4"><inist:fA14 i1="01"><s1>UCL Crypto Group, Laboratoire de Microelectronique, Universite Catholique de Louvain, Place du Levant, 3</s1><s2>1348 Louvain-La-Neuve</s2><s3>BEL</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ><sZ>3 aut.</sZ><sZ>4 aut.</sZ></inist:fA14><country>Belgique</country><placeName><region type="land" nuts="2">Vienne (Autriche)</region><settlement type="city">Vienne (Autriche)</settlement></placeName><orgName type="university">Université catholique de Louvain</orgName></affiliation></author><author><name sortKey="Rouvroy, Gael" sort="Rouvroy, Gael" uniqKey="Rouvroy G" first="Gael" last="Rouvroy">Gael Rouvroy</name><affiliation wicri:level="4"><inist:fA14 i1="01"><s1>UCL Crypto Group, Laboratoire de Microelectronique, Universite Catholique de Louvain, Place du Levant, 3</s1><s2>1348 Louvain-La-Neuve</s2><s3>BEL</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ><sZ>3 aut.</sZ><sZ>4 aut.</sZ></inist:fA14><country>Belgique</country><placeName><region type="land" nuts="2">Vienne (Autriche)</region><settlement type="city">Vienne (Autriche)</settlement></placeName><orgName type="university">Université catholique de Louvain</orgName></affiliation></author><author><name sortKey="Quisquater, Jean Jacques" sort="Quisquater, Jean Jacques" uniqKey="Quisquater J" first="Jean-Jacques" last="Quisquater">Jean-Jacques Quisquater</name><affiliation wicri:level="4"><inist:fA14 i1="01"><s1>UCL Crypto Group, Laboratoire de Microelectronique, Universite Catholique de Louvain, Place du Levant, 3</s1><s2>1348 Louvain-La-Neuve</s2><s3>BEL</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ><sZ>3 aut.</sZ><sZ>4 aut.</sZ></inist:fA14><country>Belgique</country><placeName><region type="land" nuts="2">Vienne (Autriche)</region><settlement type="city">Vienne (Autriche)</settlement></placeName><orgName type="university">Université catholique de Louvain</orgName></affiliation></author><author><name sortKey="Legat, Jean Didier" sort="Legat, Jean Didier" uniqKey="Legat J" first="Jean-Didier" last="Legat">Jean-Didier Legat</name><affiliation wicri:level="4"><inist:fA14 i1="01"><s1>UCL Crypto Group, Laboratoire de Microelectronique, Universite Catholique de Louvain, Place du Levant, 3</s1><s2>1348 Louvain-La-Neuve</s2><s3>BEL</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ><sZ>3 aut.</sZ><sZ>4 aut.</sZ></inist:fA14><country>Belgique</country><placeName><region type="land" nuts="2">Vienne (Autriche)</region><settlement type="city">Vienne (Autriche)</settlement></placeName><orgName type="university">Université catholique de Louvain</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">03-0249030</idno><date when="2002">2002</date><idno type="stanalyst">PASCAL 03-0249030 INIST</idno><idno type="RBID">Pascal:03-0249030</idno><idno type="wicri:Area/PascalFrancis/Corpus">000138</idno><idno type="wicri:Area/PascalFrancis/Curation">000019</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000121</idno><idno type="wicri:doubleKey">0302-9743:2002:Standaert F:a:time:memory</idno><idno type="wicri:Area/Main/Merge">001A65</idno><idno type="wicri:Area/Main/Curation">001A55</idno><idno type="wicri:Area/Main/Exploration">001A55</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">A time-memory tradeoff using distinguished points: New analysis & FPGA results</title><author><name sortKey="Standaert, Francois Xavier" sort="Standaert, Francois Xavier" uniqKey="Standaert F" first="Francois-Xavier" last="Standaert">Francois-Xavier Standaert</name><affiliation wicri:level="4"><inist:fA14 i1="01"><s1>UCL Crypto Group, Laboratoire de Microelectronique, Universite Catholique de Louvain, Place du Levant, 3</s1><s2>1348 Louvain-La-Neuve</s2><s3>BEL</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ><sZ>3 aut.</sZ><sZ>4 aut.</sZ></inist:fA14><country>Belgique</country><placeName><region type="land" nuts="2">Vienne (Autriche)</region><settlement type="city">Vienne (Autriche)</settlement></placeName><orgName type="university">Université catholique de Louvain</orgName></affiliation></author><author><name sortKey="Rouvroy, Gael" sort="Rouvroy, Gael" uniqKey="Rouvroy G" first="Gael" last="Rouvroy">Gael Rouvroy</name><affiliation wicri:level="4"><inist:fA14 i1="01"><s1>UCL Crypto Group, Laboratoire de Microelectronique, Universite Catholique de Louvain, Place du Levant, 3</s1><s2>1348 Louvain-La-Neuve</s2><s3>BEL</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ><sZ>3 aut.</sZ><sZ>4 aut.</sZ></inist:fA14><country>Belgique</country><placeName><region type="land" nuts="2">Vienne (Autriche)</region><settlement type="city">Vienne (Autriche)</settlement></placeName><orgName type="university">Université catholique de Louvain</orgName></affiliation></author><author><name sortKey="Quisquater, Jean Jacques" sort="Quisquater, Jean Jacques" uniqKey="Quisquater J" first="Jean-Jacques" last="Quisquater">Jean-Jacques Quisquater</name><affiliation wicri:level="4"><inist:fA14 i1="01"><s1>UCL Crypto Group, Laboratoire de Microelectronique, Universite Catholique de Louvain, Place du Levant, 3</s1><s2>1348 Louvain-La-Neuve</s2><s3>BEL</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ><sZ>3 aut.</sZ><sZ>4 aut.</sZ></inist:fA14><country>Belgique</country><placeName><region type="land" nuts="2">Vienne (Autriche)</region><settlement type="city">Vienne (Autriche)</settlement></placeName><orgName type="university">Université catholique de Louvain</orgName></affiliation></author><author><name sortKey="Legat, Jean Didier" sort="Legat, Jean Didier" uniqKey="Legat J" first="Jean-Didier" last="Legat">Jean-Didier Legat</name><affiliation wicri:level="4"><inist:fA14 i1="01"><s1>UCL Crypto Group, Laboratoire de Microelectronique, Universite Catholique de Louvain, Place du Levant, 3</s1><s2>1348 Louvain-La-Neuve</s2><s3>BEL</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ><sZ>3 aut.</sZ><sZ>4 aut.</sZ></inist:fA14><country>Belgique</country><placeName><region type="land" nuts="2">Vienne (Autriche)</region><settlement type="city">Vienne (Autriche)</settlement></placeName><orgName type="university">Université catholique de Louvain</orgName></affiliation></author></analytic><series><title level="j" type="main">Lecture notes in computer science</title><idno type="ISSN">0302-9743</idno><imprint><date when="2002">2002</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">Lecture notes in computer science</title><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm analysis</term><term>Block ciphering</term><term>Cost function</term><term>Cryptanalysis</term><term>Cryptography</term><term>Cryptosystem</term><term>Field programmable gate array</term><term>Search key</term><term>Storage access</term><term>Time allowed</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Fonction coût</term><term>Réseau porte programmable</term><term>Cryptanalyse</term><term>Cryptographie</term><term>Accès mémoire</term><term>Analyse algorithme</term><term>Clé recherche</term><term>Délai d'exécution</term><term>Chiffrement bloc</term><term>Cryptosystème</term></keywords><keywords scheme="Wicri" type="topic" xml:lang="fr"><term>Cryptographie</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">In 1980, Martin Hellman [1] introduced the concept of cryptanalytic time-memory tradeoffs, which allows the cryptanalysis of any N key symmetric cryptosystem in O(N) operations with O(N) storage, provided a precomputation of O(N) is performed beforehand. This procedure is well known but did not lead to realistic implementations. This paper considers a cryptanalytic time-memory tradeoff using distinguished points, a method referenced to Rivest [2]. The algorithm proposed decreases the expected number of memory accesses with sensible modifications of the other parameters and allows much more realistic implementations of fast key search machines. We present a detailed analysis of the algorithm and solve theoretical open problems of previous models. We also propose efficient mask functions in terms of hardware cost and probability of success. These results were experimentally confirmed and we used a purpose-built FPGA design to perform realistic tradeoffs against DES. The resulting online attack is feasible on a single PC and we recover a 40-bit key in about 10 seconds.</div></front></TEI><affiliations><list><country><li>Belgique</li></country><region><li>Vienne (Autriche)</li></region><settlement><li>Vienne (Autriche)</li></settlement><orgName><li>Université catholique de Louvain</li></orgName></list><tree><country name="Belgique"><region name="Vienne (Autriche)"><name sortKey="Standaert, Francois Xavier" sort="Standaert, Francois Xavier" uniqKey="Standaert F" first="Francois-Xavier" last="Standaert">Francois-Xavier Standaert</name></region><name sortKey="Legat, Jean Didier" sort="Legat, Jean Didier" uniqKey="Legat J" first="Jean-Didier" last="Legat">Jean-Didier Legat</name><name sortKey="Quisquater, Jean Jacques" sort="Quisquater, Jean Jacques" uniqKey="Quisquater J" first="Jean-Jacques" last="Quisquater">Jean-Jacques Quisquater</name><name sortKey="Rouvroy, Gael" sort="Rouvroy, Gael" uniqKey="Rouvroy G" first="Gael" last="Rouvroy">Gael Rouvroy</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Belgique/explor/OpenAccessBelV2/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001A55 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 001A55 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Belgique
|area= OpenAccessBelV2
|flux= Main
|étape= Exploration
|type= RBID
|clé= Pascal:03-0249030
|texte= A time-memory tradeoff using distinguished points: New analysis & FPGA results
}}
| This area was generated with Dilib version V0.6.25. |  |